package com.yiwenup.struct._03_collect.map;

import java.util.Objects;

/**
 * 哈希表实现：遍历能按照插入顺序
 **/
public class LinkedHashMap<K, V> extends HashMap<K, V> {
    private LinkedNode<K, V> head;
    private LinkedNode<K, V> tail;

    @Override
    protected Node<K, V> createNode(K key, V value, Node<K, V> parent) {
        LinkedNode<K, V> linkedNode = new LinkedNode<>(key, value, parent);

        // 搭线
        if (head == null) {
            head = tail = linkedNode;
        } else {
            tail.next = linkedNode;
            linkedNode.prev = tail;
            tail = linkedNode;
        }

        return linkedNode;
    }

    @Override
    public void clear() {
        super.clear();
        head = null;
        tail = null;
    }

    @Override
    public boolean containsValue(V value) {
        LinkedNode<K, V> node = this.head;
        while (node != null) {
            if (Objects.equals(value, node.value)) return true;
            node = node.next;
        }
        return false;
    }

    @Override
    public void traversal(Visitor<K, V> visitor) {
        LinkedNode<K, V> node = this.head;

        while (node != null) {
            if (visitor.visit(node.key, node.value)) return;
            node = node.next;
        }
    }

    @Override
    protected void afterRemove(Node<K, V> pointNode, Node<K, V> replaceNode) {
        LinkedNode<K, V> linkedPointNode = (LinkedNode<K, V>) pointNode;
        LinkedNode<K, V> linkedReplaceNode = (LinkedNode<K, V>) replaceNode;

        if (linkedPointNode != linkedReplaceNode) {
            // 交换（删除度为2的节点情况）
            // 交换prev
            LinkedNode<K, V> tmp = linkedPointNode.prev;
            linkedPointNode.prev = linkedReplaceNode.prev;
            linkedReplaceNode.prev = tmp;
            if (linkedPointNode.prev == null) {
                head = linkedPointNode;
            } else {
                linkedPointNode.prev.next = linkedPointNode;
            }
            if (linkedReplaceNode.prev == null) {
                head = linkedReplaceNode;
            } else {
                linkedReplaceNode.prev.next = linkedReplaceNode;
            }
            // 交换next
            tmp = linkedPointNode.next;
            linkedPointNode.next = linkedReplaceNode.next;
            linkedReplaceNode.next = tmp;
            if (linkedPointNode.next == null) {
                tail = linkedPointNode;
            } else {
                linkedPointNode.next.prev = linkedPointNode;
            }
            if (linkedReplaceNode.next == null) {
                tail = linkedReplaceNode;
            } else {
                linkedReplaceNode.next.prev = linkedReplaceNode;
            }
        }

        LinkedNode<K, V> prev = linkedReplaceNode.prev;
        LinkedNode<K, V> next = linkedReplaceNode.next;

        if (prev == null) {
            head = next;
        } else {
            prev.next = next;
        }

        if (next == null) {
            tail = prev;
        } else {
            next.prev = prev;
        }
    }

    private static class LinkedNode<K, V> extends Node<K, V> {
        LinkedNode<K, V> prev;
        LinkedNode<K, V> next;

        public LinkedNode(K key, V value, Node<K, V> parent) {
            super(key, value, parent);
        }
    }
}
